class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        srand(time(nullptr));
        qsort_topk(stock, 0, stock.size() - 1, cnt);
        return {stock.begin(), stock.begin() + cnt};
    }
 
    void qsort_topk(vector<int>& arr, int begin, int end, int k)
    {   // 把数组前k个小的丢到前面，不一定有序
        if(begin >= end)
            return ;
        
        int key = arr[rand() % (end - begin + 1) + begin];
        int i = begin, left = begin - 1, right = end + 1;
        while(i < right)
        {
            if(arr[i] < key)
                swap(arr[++left], arr[i++]);
            else if(arr[i] == key)
                ++i;
            else
                swap(arr[--right], arr[i]);
        }
 
        // [begin, left] [left+1, right-1] [right, end]
        int a = left - begin + 1; // 左区间元素个数
        int b = right - left - 1; // 中间区间元素个数
        if(a > k)
            qsort_topk(arr, begin, left, k);
        else if(a + b >= k)
            return;
        else // 到第三区间找k - a - b小的
            qsort_topk(arr, right, end, k - a - b);
    }
};